#include <iostream>
#include <vector>

using namespace std;
// 快速排序
void Quicksort(vector<int>& arry, int L, int R)
{
  if (L >= R)  // 大于可以return一些非法情况
    return;
  int left = L, right = R;
  // 以pivot作为中轴
  int pivot = arry[left];

  //第一次快排，条件都包含一个left<right
  while (left < right)
  {
    // 对称结构A
    // 1.1右指针指向的值大于=pivot, right--
    while (left < right && arry[right] >= pivot)
    {
      right--;
    }
    // 1.2右指针指向的值小于pivot, 该值放到left指针处
    if (left < right)
    {
      arry[left] = arry[right];
    }

    // 对称结构A
    // 2.1左指针指向的值小于=pivot, left++
    while (left < right && arry[left] <= pivot)
    {
      left++;
    }
    // 2.2左指针指向的值大于pivot, 该值放到right指针处
    if (left < right)
    {
      arry[right] = arry[left];
    }

    // 相等换回pivot
    // L和R会在序列的某个位置相遇：重合，再把pivot的值放在重合的位置
    if (left == right)
    {
      arry[left] = pivot;
    }
  }
  // 经过上面一个快排，pivot左边的子序列<=pivot, pivot右边的子序列>=pivot
  // 至于左右子序列，可能现在是无序的

  //递归，左右子串快排
  Quicksort(arry, L, right - 1);  // 此时right=pivot-> [0, pivot-1] 中轴左边
  Quicksort(arry, right + 1, R);  // [pivot+1, R] 中轴右边
}

int main()
{
  vector<int> arr = {5, 2, 9, 4, 6};
  Quicksort(arr, 0, arr.size() - 1);

  return 0;
}